// 给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

// 如果可以完成上述分割，则返回 true ；否则，返回 false 。

//  

// 示例 1：

// 输入: [1,2,3,3,4,5]
// 输出: True
// 解释:
// 你可以分割出这样两个连续子序列 : 
// 1, 2, 3
// 3, 4, 5
//  

// 示例 2：

// 输入: [1,2,3,3,4,4,5,5]
// 输出: True
// 解释:
// 你可以分割出这样两个连续子序列 : 
// 1, 2, 3, 4, 5
// 3, 4, 5
//  

// 示例 3：

// 输入: [1,2,3,4,4,5]
// 输出: False
//  

// 提示：

// 输入的数组长度范围为 [1, 10000]

#include "stdc++.h"

/* 哈希表 + 最小堆
*/
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mp{};
        for (auto& num : nums) {
            if (mp.find(num) == mp.end()) {
                mp[num] = priority_queue<int, vector<int>, greater<int>>{};
            }
            if (mp.find(num - 1) != mp.end()) {
                int preLength = mp[num - 1].top();
                mp[num - 1].pop();
                if (mp[num - 1].empty()) {
                    mp.erase(num - 1);
                }
                mp[num].push(preLength + 1);
            } else {
                mp[num].push(1);
            }
        }
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            priority_queue<int, vector<int>, greater<int>> q = it->second;
            if (q.top() < 3) {
                return false;
            }
        }
        return true;
    }
};

/* 贪心
*/
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> countMap{};
        unordered_map<int, int> endMap{};
        for (auto& num : nums) {
            int count = countMap[num] + 1;
            countMap[num] = count;
        }
        for (auto& num : nums) {
            int count = countMap[num];
            if (count > 0) {
                int preEndCount = endMap[num - 1];
                if (preEndCount > 0) {
                    countMap[num] = count - 1;
                    endMap[num - 1] = preEndCount - 1;
                    endMap[num] = endMap[num] + 1;
                } else {
                    int count1 = countMap[num + 1];
                    int count2 = countMap[num + 2];
                    if (count1 > 0 && count2 > 0) {
                        countMap[num] = count - 1;
                        countMap[num + 1] = count1 - 1;
                        countMap[num + 2] = count2 - 1;
                        endMap[num + 2] = endMap[num + 2] + 1;
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};